// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

// 思路：单调栈，维护一个单调递减栈，当遇到右侧大于单调栈栈头的元素时，此时出现凹槽，栈头左边一个是左边界，当前元素是有边界，记录其面积
// 时间复杂度：O(n)，n是height的长度
// 空间复杂度：O(n)，stack的大小

function trap(arr) {
    let stack = [0]
    let ans = 0
    for (let i = 0; i < arr.length; i++) {
        while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
            let mid = stack.pop()
            if (stack.length) {
                let leftIndex = stack[stack.length - 1]
                let h = Math.min(arr[leftIndex], arr[i]) - arr[mid]
                ans += h * (i - leftIndex - 1)
            }
        }   
        stack.push(i)     
    }
    return ans
}

let height = [0,1,0,2,1,0,1,3,2,1,2,1]
console.log(trap(height))